﻿#pragma once
#include "stdafx.h"

//class Recursion {
//public:
//	Recursion() {}
//	virtual ~Recursion() {}
//};

//1.3.3 线性O(n)
//	 问题与算法
//	考查如下问题：计算给定n个整数的总和。该问题可由代码1.3中的算法sumI()解决。
int sumCirle(int A[], int n) { //数组求和算法（迭代版）
	int sum = 0; //刜始化累计器，O(1)
	for (int i = 0; i < n; i++) //对全部共O(n)个元素，逐一
		sum += A[i]; //累计，O(1)
	return sum; //迒回累计值，O(1)
} //O(1) + O(n)*O(1) + O(1) = O(n+2) = O(n)

  //1.4.1 线性递归
//n => Length
int sumLine(int A[], int n) { //数组求和算法（线性逑弻版）
	if (1 > n) //平凡情况，递归基
		return 0; //直接（非递归式）计算
	else //一般情况
		//length = n-1
		return sumLine(A, n - 1) + A[n - 1]; //逑弻：前n - 1顷乀和，再累计第n - 1顷
} //O(1)*逑弻深度 = O(1)*(n + 1) = O(n)

//线性递归
//算法sum()可能朝着更深一层进行自我调用，且每一递归实例对自身的调用至多一次。于是，
//每一层次上至多只有一个实例，且它们构成一个线性的次序关系。此类递归模式因而称作“线性
//递归”（linear recursion），它也是递归的最基本形式。
//这种形式中，应用问题总可分解为两个独立的子问题：其一对应于单独的某个元素，故可直
//接求解（比如A[n - 1]）；另一个对应于剩余部分，且其结构与原问题相同（比如sum(A, n -
//	1)）。另外，子问题的解经简单的合并（比如整数相加）之后，即可得到原问题的解。
//	 减而治之
//	线性递归的模式，往往对应于所谓减而治之（decrease - and-conquer）的算法策略：递归
//	每深入一层，待求解问题的规模都缩减一个常数，直至最终蜕化为平凡的小（简单）问题。
//	按照减而治之策略，此处随着递归的深入，调用参数将单调地线性递减。因此无论最初输入
//	的n有多大，递归调用的总次数都是有限的，故算法的执行迟早会终止，即满足有穷性。当抵达
//	递归基时，算法将执行非递归的计算（这里是返回0）。


